class Solution:

    """
     方法： 使用动态规划求解唯一路径问题
            使用一维数组f[j]表示到达当前行第j列的路径数
            每个位置的路径数等于其上方和左方路径数之和
     
     Args:
         m: int - 网格的行数
         n: int - 网格的列数
     
     Returns:
         int: 从左上角到右下角的唯一路径数
     
     Time: O(m*n) - 需要遍历整个网格
     
     Space: O(n) - 使用一维数组存储中间结果
     """
    def uniquePaths(self, m: int, n: int) -> int:
         f = [0] * (n+1)
         f[1] = 1
         for _ in range(m):
            for j in range(n):
                f[j+1] += f[j]
         return f[n] 
    
    def combo(self, n: int, k:int) -> int:
        k = min(k, n-k)
        res = 1
        for i in range (1, k + 1):
            res = res * (n + 1 - i) // i 
        return res

    """
     方法： 使用组合数学公式计算从起点到终点的唯一路径数
            从m+n-2步中选择m-1步向下移动的组合数
            使用组合数公式C(n,k) = n!/(k!(n-k)!)
     
     Args:
         m: int - 网格的行数
         n: int - 网格的列数
     
     Returns:
         int: 从左上角到右下角的唯一路径数
     
     Time: O(min(m,n)) - 计算组合数时循环min(m,n)次
     
     Space: O(1) - 只使用常数额外空间
     """
    def uniquePaths(self, m: int, n: int) -> int:
       return self.combo(m+n-2,m-1)
    